package 线段树并查集字典树;

import java.util.Arrays;

public class segmentTree<E> {
    private E[]data;
    private E[]tree;
    private Merger<E> merger;

    public segmentTree(E[] arr, Merger<E> merger) {
        this.merger = merger;
        this.data = (E[])new Object[arr.length];
        for (int i = 0; i < arr.length; i++) {
            data[i] = arr[i];
        }
        tree = (E[])new Object[4*arr.length];
        buildSegmentTree(0, 0, data.length - 1);
    }
    public E query(int queryL,int queryR){
        return query(0, 0, data.length - 1, queryL, queryR);
    }
//    在treeIndex 【l,r]的线段树查找区间
    public E query(int treeIndex, int l, int r, int queryL,int queryR){
        if(l == queryL && r == queryR){
            return tree[treeIndex];
        }
        int mid = (l+r)/2;
        int leftIndex = 2 * treeIndex + 1;
        int rightIndex = 2 * treeIndex + 2;
        if(queryR <= mid)
        return query(leftIndex, l, mid, queryL, queryR);
        else if(queryL >= mid+1)
        return query(rightIndex, mid + 1, r, queryL, queryR);
        else{
            return merger.merge(
                    query(leftIndex, l, mid, queryL, mid),
                    query(rightIndex, mid + 1, r, mid+1, queryR)
            );
        }
    }
    public void set(int index, E e){
        data[index] = e;
    }
//    在treeIndex创建区间【l,r]的线段树
    private void buildSegmentTree(int treeIndex, int l, int r) {
        if(l == r)
        {
            tree[treeIndex] = data[l];
            return;
        }
        int leftIndex = 2 * treeIndex + 1;
        int rightIndex = 2 * treeIndex + 2;
        int mid = (l+r)/2;
        buildSegmentTree(leftIndex, l, mid);
        buildSegmentTree(rightIndex, mid+1, r);
        tree[treeIndex] = merger.merge(tree[leftIndex] , tree[rightIndex]);

    }

    public int getSize(){
        return data.length;
    }
    public E get(int index){
        return data[index];
    }

    @Override
    public String toString() {
        return "segmentTree{" +
                "data=" + Arrays.toString(data) +
                ", tree=" + Arrays.toString(tree);
    }

    public static void main(String[] args) {
        Integer arr[] = {1,2,3,4,5,6};
        segmentTree<Integer> tree = new segmentTree<>(arr, new Merger<Integer>() {
            @Override
            public Integer merge(Integer a, Integer b) {
                return a + b;
            }
        });
        System.out.println(tree.toString());
        System.out.println(tree.query(0,5));

    }





}
